{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数 <code>n</code> 和 <code>k</code>，返回范围 <code>[1, n]</code> 中所有可能的 <code>k</code> 个数的组合。</p>\n",
    "\n",
    "<p>你可以按 <strong>任何顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, k = 2\n",
    "<strong>输出：</strong>\n",
    "[\n",
    "  [2,4],\n",
    "  [3,4],\n",
    "  [2,3],\n",
    "  [1,2],\n",
    "  [1,3],\n",
    "  [1,4],\n",
    "]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, k = 1\n",
    "<strong>输出：</strong>[[1]]</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 20</code></li>\n",
    "\t<li><code>1 <= k <= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [combinations](https://leetcode.cn/problems/combinations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [combinations](https://leetcode.cn/problems/combinations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n2', '1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def dfs(n,arr,k):\n",
    "            if k <= 0 :\n",
    "                return arr\n",
    "            ans = []\n",
    "            for idx in range(len(arr)):\n",
    "                for i in range(arr[idx][-1]+1,n+1):\n",
    "                    ans.append(arr[idx] + [i])\n",
    "            return dfs(n,ans,k-1)\n",
    "        return dfs(n,[[i] for i in range(1,n-k+2)],k-1)\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        def add(s,arr):\n",
    "            ss = \"\"\n",
    "            idx = 0\n",
    "            for num in arr:\n",
    "                ss += (s[idx:num] + \".\")\n",
    "                idx = num\n",
    "            return ss + s[idx:]\n",
    "        def judge(s):\n",
    "            ss = s.split(\".\")\n",
    "            for sss in ss:\n",
    "                if int(sss) > 255 or (sss[0] == \"0\" and len(sss) > 1):\n",
    "                    return False\n",
    "            return True\n",
    "        n = len(s)\n",
    "        if n == 4:\n",
    "            return [f\"{s[0]}.{s[1]}.{s[2]}.{s[3]}\"]\n",
    "        elif n < 4:\n",
    "            return []\n",
    "        elif n == 12:\n",
    "            ss = f\"{s[:3]}.{s[3:6]}.{s[6:9]}.{s[9:12]}\"\n",
    "            if judge(ss):\n",
    "                return [ss]\n",
    "            else:\n",
    "                return []\n",
    "\n",
    "        if len(s) > 12:\n",
    "            return []\n",
    "        ans = []\n",
    "        conbines = self.combine(n-1,3)\n",
    "        for conbine in conbines:\n",
    "            if conbine[1]-conbine[0] > 3 or conbine[2]-conbine[1] > 3 or n-conbine[2] > 3:\n",
    "                continue\n",
    "            ss = add(s,conbine)\n",
    "            if judge(ss):\n",
    "                ans.append(ss)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        combine = []\n",
    "        freq = sorted(collections.Counter(candidates).items())\n",
    "        n = len(freq)\n",
    "        \n",
    "        def dfs(target: int, idx: int) -> None:\n",
    "            nonlocal combine\n",
    "\n",
    "            if target == 0:\n",
    "                ans.append(combine[:])\n",
    "                return\n",
    "\n",
    "            if idx == n or target < freq[idx][0]:\n",
    "                return\n",
    "            \n",
    "            dfs(target, idx + 1)\n",
    "\n",
    "            most = min(freq[idx][1], target // freq[idx][0])\n",
    "            for i in range(1, most+1):\n",
    "                combine.append(freq[idx][0])\n",
    "                dfs(target - i * freq[idx][0], idx + 1)\n",
    "            combine = combine[:-most]\n",
    "\n",
    "        dfs(target, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self,nums:List[int])-> List[List[int]]:\n",
    "        numsLen = len(nums)\n",
    "        target = -2147483647\n",
    "        part = [target]*numsLen\n",
    "        res = []\n",
    "        def combine(n,partRes):\n",
    "            nonlocal numsLen,res,target,nums \n",
    "            if n == numsLen:\n",
    "                if partRes not in res:\n",
    "                    res.append(partRes)\n",
    "                return\n",
    "            num = nums[n]\n",
    "            for i in range(numsLen):\n",
    "                if partRes[i]==target:\n",
    "                    finalRes = partRes.copy()\n",
    "                    finalRes[i] = num\n",
    "                    combine(n+1,finalRes)\n",
    "        combine(0,part)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    "Question: combine accounts that have the same email, return them in a list of name and emails(asc)\n",
    "input: account [[name, emails...]]\n",
    "reutrn: [[name, emails asc]]\n",
    "constraints:\n",
    "- there are at least 1 account\n",
    "- there are at least 1 email in each account\n",
    "------------------------------\n",
    "store every email as their own root\n",
    "go through accounts, union email\n",
    "name:\n",
    "\"\"\"\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        \"\"\" initialize each eamil as a distinct set \"\"\"\n",
    "        # label email from 0\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "        self.set_count = n\n",
    "\n",
    "    def find(self, num) -> int:\n",
    "        \"\"\" return the root parent of num, compress path \"\"\"\n",
    "        if self.parent[num] != num:\n",
    "            self.parent[num] = self.find(self.parent[num])\n",
    "        return self.parent[num]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "\n",
    "        # need union\n",
    "        if rootx != rooty:\n",
    "            if self.rank[rootx] < self.rank[rooty]:\n",
    "                rootx, rooty = rooty, rootx\n",
    "            # attach rooty(shorter) to rootx(higher)\n",
    "            self.parent[rooty] = rootx\n",
    "            if self.rank[rooty] == self.rank[rootx]:\n",
    "                self.rank[rootx] += 1\n",
    "            self.set_count -= 1\n",
    "\n",
    "    def is_connected(self, x, y) -> bool:\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:\n",
    "        # label every email to a distinct number\n",
    "        # record owner's name of each email\n",
    "        email_num = {}\n",
    "        email_name = {}\n",
    "        for account in accounts:\n",
    "            for email in account[1:]:\n",
    "                if email not in email_num:\n",
    "                    email_num[email] = len(email_num)\n",
    "                    email_name[email] = account[0]\n",
    "        \n",
    "        uf = UnionFind(len(email_num))\n",
    "        # union all emails in the same account\n",
    "        for account in accounts:\n",
    "            first_num = email_num[account[1]]\n",
    "            for other_num in account[2:]:\n",
    "                uf.union(first_num, email_num[other_num])\n",
    "\n",
    "        # group emails by their root\n",
    "        root_email = collections.defaultdict(list)\n",
    "        for email, num in email_num.items():\n",
    "            root = uf.find(num)\n",
    "            root_email[root].append(email)\n",
    "        \n",
    "        ans = []\n",
    "        for emails in root_email.values():\n",
    "            ans.append([email_name[emails[0]]] + sorted(emails))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        bold = [False] * n\n",
    "        # iterate through every index position of string\n",
    "        # for every index position, iterate through every word to check if it is a prefix of current substring, if so, mark is as bolded\n",
    "        for i in range(n):\n",
    "            for w in words:\n",
    "                if s[i:].startswith(w):\n",
    "                    bold[i:i+len(w)] = [True] * len(w)\n",
    "        # combine all the bolded booleans into bold tags\n",
    "        res = \"\"\n",
    "        for i in range(n):\n",
    "            # current position is the start of bold\n",
    "            if bold[i] and (i == 0 or not bold[i-1]):\n",
    "                res += \"<b>\"\n",
    "            res += s[i]\n",
    "            # current position is the end of bold\n",
    "            if bold[i] and (i == n-1 or not bold[i+1]):\n",
    "                res += \"</b>\"\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        mem = collections.defaultdict(list)\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym[1: -1].split(\",\")\n",
    "            mem[name1].append(name2)\n",
    "            mem[name2].append(name1)\n",
    "\n",
    "        #print(mem)\n",
    "        def combine_synonym(name, current_list, visited):\n",
    "            queue = [name]\n",
    "            next_queue = []\n",
    "\n",
    "            while queue:\n",
    "                for name in queue:\n",
    "                    if name in visited:\n",
    "                        continue\n",
    "                    current_list.append(name)\n",
    "                    visited.add(name)\n",
    "                    for synony in mem[name]:\n",
    "                        next_queue.append(synony)\n",
    "                queue = next_queue\n",
    "                next_queue = []\n",
    "\n",
    "        names_map = {}\n",
    "        for name in mem:\n",
    "            if name in names_map:\n",
    "                continue\n",
    "            found_names = []\n",
    "            combine_synonym(name, found_names, set())\n",
    "            first_name = min(found_names)\n",
    "            for found_name in found_names:\n",
    "                names_map[found_name] = first_name\n",
    "\n",
    "        #print(names_map)\n",
    "        \n",
    "        counter = collections.defaultdict(int)\n",
    "        for name_str in names:\n",
    "            name, freq = name_str.split(\"(\")[0], int(name_str.split(\"(\")[1][:-1])\n",
    "            if name in names_map:\n",
    "                counter[names_map[name]] += freq\n",
    "            else:\n",
    "                counter[name] += freq\n",
    "\n",
    "        ret = []\n",
    "        for name, freq in counter.items():\n",
    "            ret.append(name + \"(\" + str(freq) + \")\")\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Poly(Counter):\n",
    "    def __add__(self,other):\n",
    "        self.update(other)\n",
    "        return self\n",
    "    def __sub__(self,other):\n",
    "        self.update({k:-v for k,v in other.items()})\n",
    "        return self\n",
    "    def __mul__(self,other):\n",
    "        ans = Poly()\n",
    "        for k1,v1 in self.items():\n",
    "            for k2,v2 in other.items():\n",
    "                ans.update({tuple(sorted(k1+k2)):v1*v2})\n",
    "        return ans\n",
    "    def evaluate(self, evalmap):\n",
    "        ans = Poly()\n",
    "        for k,c in self.items():\n",
    "            free = []\n",
    "            for token in k:\n",
    "                if token in evalmap:\n",
    "                    c *= evalmap[token]\n",
    "                else:\n",
    "                    free.append(token)\n",
    "            ans[tuple(free)] += c\n",
    "        return ans\n",
    " \n",
    "    def to_list(self):\n",
    "        return [\"*\".join((str(v),) + k)\n",
    "                for k, v in sorted(self.items(),\n",
    "                    key = lambda x: (-len(x[0]), x[0], x[1]))\n",
    "                if v]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        evalmap = dict(zip(evalvars,evalints))\n",
    "\n",
    "        def combine(left,right,symbol):\n",
    "            if symbol == '+':return left+right\n",
    "            if symbol == '-':return left-right\n",
    "            if symbol == '*':return left*right\n",
    "\n",
    "        def make(expr):\n",
    "            ans = Poly()\n",
    "            if expr.isdigit():\n",
    "                ans.update({():int(expr)})\n",
    "            else:\n",
    "                ans[tuple([expr])] += 1\n",
    "            return ans\n",
    "        \n",
    "        def parse(expr):\n",
    "            bucket = []\n",
    "            symbols = []\n",
    "            i = 0\n",
    "            while i<len(expr):\n",
    "                if expr[i] == '(':\n",
    "                    bal = 0\n",
    "                    for j in range(i,len(expr)):\n",
    "                        if expr[j] == '(':bal+=1\n",
    "                        if expr[j] == ')':bal-=1\n",
    "                        if bal == 0:break\n",
    "                    \n",
    "                    try:\n",
    "                        bucket.append(parse(expr[i+1:j]))\n",
    "                    except Exception as e:\n",
    "                        print(expr[i+1:j])\n",
    "                    i = j\n",
    "                elif expr[i].isalnum():\n",
    "                    for j in range(i,len(expr)):\n",
    "                        if expr[j]==' ':\n",
    "                            bucket.append(make(expr[i:j]))\n",
    "                            break\n",
    "                    else:\n",
    "                        bucket.append(make(expr[i:]))\n",
    "                    i = j\n",
    "                elif expr[i] in \"+-*\":\n",
    "                    symbols.append(expr[i])\n",
    "                i += 1\n",
    "            \n",
    "            for i in range(len(symbols)-1,-1,-1):\n",
    "                if symbols[i] == '*':\n",
    "                    bucket[i] = combine(bucket[i], bucket.pop(i+1),symbols.pop(i))\n",
    "   \n",
    "            ans = bucket[0]\n",
    "            for i,symbol in enumerate(symbols,1):\n",
    "                ans = combine(ans,bucket[i],symbol)\n",
    "            return ans\n",
    "\n",
    "        P = parse(expression).evaluate(evalmap)\n",
    "        return P.to_list()\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Poly:\n",
    "    def __init__(self):\n",
    "        self.d = defaultdict(int)\n",
    "\n",
    "    def add(self, x):\n",
    "        for k, v in x.items():\n",
    "            self.d[k] += v\n",
    "\n",
    "    def sub(self, x):\n",
    "        for k, v in x.items():\n",
    "            self.d[k] -= v\n",
    "\n",
    "    def mul(self, x):\n",
    "        tmp = defaultdict(int)\n",
    "        for k1, v1 in self.d.items():\n",
    "            for k2, v2 in x.items():\n",
    "                tmp[tuple(sorted(k1 + k2))] += v1 * v2\n",
    "\n",
    "        self.d = tmp\n",
    "\n",
    "    def evaluate(self, m):\n",
    "        tmp = defaultdict(int)\n",
    "        for k, v in self.d.items():\n",
    "            s = []\n",
    "            for kk in k:\n",
    "                if kk in m:\n",
    "                    v *= m[kk]\n",
    "                else:\n",
    "                    s.append(kk)\n",
    "\n",
    "            tmp[tuple(s)] += v\n",
    "\n",
    "        self.d = tmp\n",
    "\n",
    "    def to_list(self):\n",
    "        ret = []\n",
    "        for k in sorted(self.d.keys(), key=lambda x: (-len(x), x)):\n",
    "            if k != () and self.d[k] != 0:\n",
    "                ret.append('*'.join((str(self.d[k]),) + k))\n",
    "\n",
    "        if () in self.d and self.d[()] != 0:\n",
    "            ret.append(str(self.d[()]))\n",
    "        \n",
    "        return ret\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.d)\n",
    "\n",
    "class Solution:\n",
    "    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:\n",
    "        tokens = [x for x in re.split(r'([\\(\\)\\+\\-\\*])', expression.replace(' ', '')) if x != '']\n",
    "\n",
    "        n = len(tokens)\n",
    "\n",
    "        values = dict(zip(evalvars, evalints))\n",
    "\n",
    "        def combine(left, right, symbol):\n",
    "            if symbol == '+':\n",
    "                left.add(right.d)\n",
    "            elif symbol == '-':\n",
    "                left.sub(right.d)\n",
    "            elif symbol == '*':\n",
    "                left.mul(right.d)\n",
    "\n",
    "            return left\n",
    "\n",
    "        def make(i):\n",
    "            expr = tokens[i]\n",
    "            ret = Poly()\n",
    "            if expr.isdigit():\n",
    "                ret.add({\n",
    "                    (): int(expr)\n",
    "                })\n",
    "            else:\n",
    "                ret.add({\n",
    "                    (expr,): 1\n",
    "                })\n",
    "            return ret\n",
    "\n",
    "        def parse(i):\n",
    "            bucket = []\n",
    "            symbols = []\n",
    "\n",
    "            while i < n:\n",
    "                if tokens[i] == '(':\n",
    "                    j, ret = parse(i + 1)\n",
    "                    bucket.append(ret)\n",
    "                    i = j\n",
    "                elif tokens[i] == ')':\n",
    "                    break\n",
    "                elif tokens[i] in '+-*':\n",
    "                    symbols.append(tokens[i])\n",
    "                else:\n",
    "                    bucket.append(make(i))\n",
    "\n",
    "                i += 1\n",
    "\n",
    "            idx = i\n",
    "\n",
    "            if not bucket:\n",
    "                return idx, Poly()    \n",
    "\n",
    "            for i in range(len(symbols) - 1, -1, -1):\n",
    "                if symbols[i] == '*':\n",
    "                    bucket[i] = combine(bucket[i], bucket.pop(i + 1), symbols.pop(i))\n",
    "\n",
    "            ret = bucket[0]\n",
    "\n",
    "            for i, s in enumerate(symbols, 1):\n",
    "                ret = combine(ret, bucket[i], s)\n",
    "\n",
    "            return idx, ret\n",
    "\n",
    "        _, ret = parse(0)\n",
    "\n",
    "        ret.evaluate(values)\n",
    "\n",
    "        return ret.to_list()\n",
    "            \n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        # combine the position and speed, then sort\n",
    "        def takefirst(ele):\n",
    "            return ele[0]\n",
    "        init = []\n",
    "        for idx in range(len(position)):\n",
    "            init.append([position[idx], speed[idx]])\n",
    "        init.sort(key = takefirst, reverse = True)\n",
    "\n",
    "        for idx, element in enumerate(init):\n",
    "            init[idx] = [element[0], element[1], (target - element[0]) / element[1]]\n",
    "        \n",
    "        res = [init[0][2]]\n",
    "        for idx in range(1, len(init)):\n",
    "            if init[idx][2] < init[idx - 1][2]:\n",
    "                init[idx][2] = init[idx - 1][2]\n",
    "            res.append(init[idx][2])\n",
    "        return len(set(res))\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "        self.result = []\n",
    "        self.path = []\n",
    "    def combinationSum2(self,candidates, target):\n",
    "        candidates.sort()\n",
    "        def backtracking(target,index):\n",
    "            if self.sum == target:\n",
    "                self.result.append(self.path[:])\n",
    "                return\n",
    "            if self.sum > target:\n",
    "                return\n",
    "\n",
    "            for i in range(index,len(candidates)):\n",
    "                if i > index and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                self.sum += candidates[i]\n",
    "                self.path.append(candidates[i])\n",
    "                \n",
    "                backtracking(target,i+1)\n",
    "\n",
    "                self.sum -= candidates[i]\n",
    "                self.path.pop()\n",
    "\n",
    "        backtracking(target,0)\n",
    "        return self.result\n",
    "\n",
    "            # last_startidx = n - (k - len(path)) + 1\n",
    "# n = 4\n",
    "# k = 2\n",
    "# print(Solution().combine(n,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        stack = [(i,) for i in range(1, n+1)]  # 初始化栈\n",
    "        while stack:\n",
    "            combination = stack.pop()\n",
    "            if len(combination) == k:\n",
    "                result.append(combination)\n",
    "            else:\n",
    "                start = combination[-1] + 1 if combination else 1\n",
    "                for i in range(start, n+1):\n",
    "                    stack.append(combination+(i,))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self) -> None:\n",
    "#         self.res = []\n",
    "#         self.path = []\n",
    "\n",
    "#     def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "#         self.backtracking(n+1,k,1)\n",
    "#         return self.res\n",
    "\n",
    "#     def backtracking(self,n,k,startindex):\n",
    "#         if len(self.path) == k:\n",
    "#            self.res.append(self.path[:])\n",
    "#            return \n",
    "#         for i in range(startindex,n):\n",
    "#             self.path.append(i)\n",
    "#             self.backtracking(n,k,i+1)\n",
    "#             self.path.pop(-1)\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return list(itertools.combinations(range(1,n+1),k))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return list(itertools.combinations(range(1, n+1), k))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return list(itertools.combinations(range(1, n+1), k))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return list(itertools.combinations(range(1,n+1),k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        vis = [0 for _ in range(n+1)]\n",
    "        def dfs(x):\n",
    "            if len(x) == k:\n",
    "                res.append(x.copy())\n",
    "                return\n",
    "            for i in range(1, n+1):\n",
    "                if vis[i]:continue\n",
    "                if len(x) > 0 and i <= x[-1]: continue\n",
    "                vis[i]=1\n",
    "                x.append(i)\n",
    "                dfs(x)\n",
    "                x.pop()\n",
    "                vis[i]=0\n",
    "        dfs([])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = list(range(1, n + 1))\n",
    "        start = 0\n",
    "        output = []\n",
    "        queue = deque()\n",
    "        queue.append(([], start))\n",
    "        len_nums = len(nums)\n",
    "\n",
    "        while queue:\n",
    "            curr = queue.popleft()\n",
    "            if len(curr[0]) == k:\n",
    "                output.append(curr[0])\n",
    "            if len(curr[0]) > k:\n",
    "                break\n",
    "\n",
    "            for i in range(curr[1], len_nums):\n",
    "                queue.append((curr[0] + [nums[i]], i+1))\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        nums = list(range(1, n + 1))\n",
    "        start = 0\n",
    "        output = []\n",
    "        queue = deque()\n",
    "        queue.append(([], start))\n",
    "        len_nums = len(nums)\n",
    "\n",
    "        while queue:\n",
    "            curr = queue.popleft()\n",
    "            if len(curr[0]) == k:\n",
    "                output.append(curr[0])\n",
    "            if len(curr[0]) > k:\n",
    "                break\n",
    "\n",
    "            for i in range(curr[1], len_nums):\n",
    "                queue.append((curr[0] + [nums[i]], i+1))\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        path,res=[],[]\n",
    "        index=1\n",
    "        self.backtracking(n,k,index,path,res)\n",
    "        return res\n",
    "\n",
    "    def backtracking(self,n,k,index,path,res):\n",
    "        if len(path)==k:\n",
    "            res.append(path[:])\n",
    "            return \n",
    "        for i in range(index,n+1):\n",
    "            path.append(i)\n",
    "            self.backtracking(n,k,i+1,path,res)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        result=[]\n",
    "        self.backtracking(n,k,1,[],result)\n",
    "        return result\n",
    "    def backtracking(self,n,k,startindex,path,result):\n",
    "        if len(path)==k:\n",
    "            result.append(path[:])\n",
    "            return\n",
    "        for i in range(startindex,n-(k-len(path))+2):\n",
    "            path.append(i)\n",
    "            print(path)\n",
    "            self.backtracking(n,k,i+1,path,result)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        result = [] \n",
    "        self.backtracking(n, k, 1, [], result)\n",
    "        return result\n",
    "    def backtracking(self, n, k, startIndex, path, result):\n",
    "        if len(path) == k:\n",
    "            result.append(path[:])\n",
    "            return\n",
    "        for i in range(startIndex, n + 1):\n",
    "            path.append(i)\n",
    "            self.backtracking(n, k, i + 1, path, result)\n",
    "            path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def backtrack(start, k, tmp):\n",
    "            if k==0:\n",
    "                res.append(tmp)\n",
    "                return \n",
    "            for j in range(start, n+1):\n",
    "                backtrack(j+1, k-1, tmp+[j])\n",
    "        backtrack(1, k, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        l = []\n",
    "        for ele in itertools.combinations(range(1, n+1), k):\n",
    "            l.append(list(ele))\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        # 方法一：从答案的角度\n",
    "        # res, path = [], []\n",
    "        # def dfs(i):\n",
    "        #     if len(path)==k:\n",
    "        #         res.append(path.copy())\n",
    "        #         return\n",
    "            \n",
    "        #     for j in range(i, n+1-k+len(path)+1):\n",
    "        #         path.append(j)\n",
    "        #         dfs(j+1)\n",
    "        #         path.pop()\n",
    "        # dfs(1)\n",
    "        # return res\n",
    "        # 方法二：选或者不选\n",
    "        res, path = [], []\n",
    "\n",
    "        def dfs(i):\n",
    "            if len(path)==k:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            if i<n-k+len(path)+2:\n",
    "                # 不选\n",
    "                dfs(i+1)\n",
    "                # 选\n",
    "                path.append(i)\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def backtracking(n, k, cur, start):\n",
    "            if len(cur) == k:\n",
    "                print(cur)\n",
    "                return [cur]\n",
    "\n",
    "            if len(cur) + n + 1 - start < k:\n",
    "                return []\n",
    "\n",
    "            res = []\n",
    "            for i in range(start, n+1):\n",
    "                # cur.append(i)\n",
    "                # print(cur + [i], i, n+1)\n",
    "                tmp = backtracking(n, k, cur + [i], i+1)\n",
    "                # cur = cur[:-1]\n",
    "                res += tmp\n",
    "                # print(res, i)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return backtracking(n, k, [], 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def backtracking(n, k, cur, start):\n",
    "            if len(cur) == k:\n",
    "                print(cur)\n",
    "                return [cur]\n",
    "\n",
    "            res = []\n",
    "            for i in range(start, n+1):\n",
    "                # cur.append(i)\n",
    "                # print(cur + [i], i, n+1)\n",
    "                tmp = backtracking(n, k, cur + [i], i+1)\n",
    "                # cur = cur[:-1]\n",
    "                res += tmp\n",
    "                # print(res, i)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return backtracking(n, k, [], 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        \"\"\"Q77 alternative\"\"\"\n",
    "        ans = []\n",
    "        if k == 1:\n",
    "            return [[i] for i in range(1, n+1)]\n",
    "        elif k == n:\n",
    "            return [[i for i in range(1, n+1)]]\n",
    "        else:\n",
    "            return [(i + [n]) for i in self.combine(n-1, k-1)] + self.combine(n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if n == k:\n",
    "            return [list(range(1,n+1))]\n",
    "        res = []\n",
    "        if k == 1:\n",
    "            for i in range(1,n+1):\n",
    "                res.append([i])\n",
    "            return res\n",
    "        for arr in self.combine(n-1,k-1):\n",
    "            res.append(arr+[n])\n",
    "        return self.combine(n-1,k) + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def get_results(start, end, k):\n",
    "            if end - start + 1 < k:\n",
    "                return []\n",
    "            if k == 0:\n",
    "                return [[]]\n",
    "            has_i = [[start] + res for res in get_results(start + 1, end, k - 1)]\n",
    "            no_i = get_results(start + 1, end, k)\n",
    "            return has_i + no_i\n",
    "        return get_results(1, n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k == 0:\n",
    "            return [[]]\n",
    "        if n == 1:\n",
    "            return [[1]]\n",
    "        results= [x + [n] for x in self.combine(n-1, k-1)] + [x for x in self.combine(n-1, k)]\n",
    "        results = [r for r in results if len(r) == k]\n",
    "        return results\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combineR(self,nums,k):\n",
    "        if k==1:\n",
    "            return [[i] for i in nums]\n",
    "        res = []\n",
    "        for j in range(len(nums)):\n",
    "            for e in self.combineR(nums[j+1:],k-1):\n",
    "                res.append([nums[j]]+e)\n",
    "        return res\n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return self.combineR(list(range(1,n+1)),k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fun(self, start: int, end: int, l: int, k: int) -> List[List[int]]:\n",
    "        if l == k: return [[]]\n",
    "        # if start > end: return []\n",
    "        res = [[start] + item for item in self.fun(start + 1, end, l + 1, k)]\n",
    "        if end - start + 1 > k - l:\n",
    "            res.extend([item for item in self.fun(start + 1, end, l, k)])\n",
    "        return res\n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return self.fun(1, n, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fun(self, start: int, end: int, l: int, k: int) -> List[List[int]]:\n",
    "        # if start > end: return []\n",
    "        if l == k - 1:\n",
    "            res = [[start]]\n",
    "        else:\n",
    "            res = [[start] + item for item in self.fun(start + 1, end, l + 1, k)]\n",
    "        if end - start + 1 > k - l:\n",
    "            res.extend([item for item in self.fun(start + 1, end, l, k)])\n",
    "        return res\n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        return self.fun(1, n, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def mycombine(l, r, k, out):\n",
    "            if k == 0:\n",
    "                res.append(out)\n",
    "                return \n",
    "            \n",
    "            if k == (r - l + 1):\n",
    "                out += range(l, r + 1)\n",
    "                res.append(out)\n",
    "                return \n",
    "            \n",
    "            for i in range(l, r + 1):\n",
    "                mycombine(i + 1, r, k - 1, out + [i])\n",
    "            \n",
    "            return \n",
    "        \n",
    "        mycombine(1, n, k, [])\n",
    "        return res\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def combine(self, n: int, k: int):\n",
    "            def recur(curList, m):\n",
    "                num = len(curList)\n",
    "                if num < m:\n",
    "                    return\n",
    "                elif num == m:\n",
    "                    return [curList]\n",
    "                elif m == 1:\n",
    "                    return [[x] for x in curList]\n",
    "                newList = []\n",
    "                while curList:\n",
    "                    j = curList.pop(0)\n",
    "                    lll = [x for x in curList]\n",
    "                    results = recur(lll, m - 1)\n",
    "                    if results:\n",
    "                        for result in results:\n",
    "                            newList.append([j] + result)\n",
    "                return newList\n",
    "            return recur(list(range(1, n + 1)), k)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def combine(self, n: int, k: int):\n",
    "            def recur(curList, m):\n",
    "                num = len(curList)\n",
    "                if num < m:\n",
    "                    return\n",
    "                elif num == m:\n",
    "                    return [curList]\n",
    "                elif m == 1:\n",
    "                    return [[x] for x in curList]\n",
    "                newList = []\n",
    "                while curList:\n",
    "                    j = curList.pop(0)\n",
    "                    lll = curList.copy()\n",
    "                    results = recur(lll, m - 1)\n",
    "                    if results:\n",
    "                        for result in results:\n",
    "                            newList.append([j] + result)\n",
    "                return newList\n",
    "            return recur(list(range(1, n + 1)), k)\n",
    "\n",
    "            \n",
    "# class Solution:\n",
    "#     def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "\n",
    "#         ##先生成数\n",
    "#         nums = [i for i in range(1,n+1)]\n",
    "#         # print(nums)\n",
    "\n",
    "#         ##明显用回溯法:\n",
    "#         res = []\n",
    "\n",
    "#         def backtrace(nums_b,curr_res,index):\n",
    "#             # print(\"curr_res:\",curr_res)\n",
    "#             if len(curr_res)==k:\n",
    "#                 res.append(curr_res[:]) ##浅拷贝，这一步很重要\n",
    "#                 return \n",
    "\n",
    "#             for i in range(index,n):\n",
    "#                 # print(i,nums_b)\n",
    "#                 curr_res.append(nums[i])\n",
    "#                 backtrace(nums_b[index:],curr_res,i+1)\n",
    "#                 curr_res.pop()\n",
    "\n",
    "#         ##特殊情况处理\n",
    "#         if n==0 or k==0:\n",
    "#             return res\n",
    "\n",
    "#         backtrace(nums,[],0)\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def func(nums, k):\n",
    "            if k == 1:\n",
    "                return [[ele] for ele in nums]\n",
    "            else:\n",
    "                n = len(nums)\n",
    "                res = []\n",
    "                for i in range(1, n + 1):\n",
    "                    num = nums[i-1]\n",
    "                    combi = func(nums[i:], k - 1)\n",
    "                    for ele in combi:\n",
    "                        res.append([num] + ele)\n",
    "                return res\n",
    "                \n",
    "        nums = [i for i in range(1,n+1)]\n",
    "        return func(nums,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        result=[]\n",
    "        for i in range(n,k-1,-1):\n",
    "            if k==1:\n",
    "                result.append([i])\n",
    "                continue\n",
    "            _r=self.combine(i-1,k-1)\n",
    "            for item in _r:\n",
    "                result.append(item+[i])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = [[x] for x in range(1, n-k+2)]\n",
    "        for j in range(1, k):\n",
    "            ans = [an + [i] for an in ans for i in range(an[-1] + 1, n - k + 2 + j)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int):\n",
    "        pre_conseq=[]\n",
    "        conseq=[[x] for x in range(1,n-k+2)]\n",
    "        for now_k in range(2,k+1):\n",
    "            #del pre_conseq\n",
    "            pre_conseq=conseq\n",
    "            #del conseq\n",
    "            conseq=[]\n",
    "            for pre_nums in pre_conseq:\n",
    "                for new_num in range(pre_nums[-1]+1,n+now_k-k+1):\n",
    "                    conseq.append(pre_nums+[new_num])\n",
    "        del pre_conseq\n",
    "        return conseq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def com(nums, k):\n",
    "            if k == 0:\n",
    "                return [[]]\n",
    "            if k == 1:\n",
    "                return [[x] for x in nums]\n",
    "            output = []\n",
    "            for i in range(len(nums)):\n",
    "                a = com(nums[i+1:], k-1)\n",
    "                # b = [x.append(nums[i]) for x in a]\n",
    "                b = [x + [nums[i]] for x in a]\n",
    "                output += b\n",
    "            return output\n",
    "        nums = list(range(1, n+1))\n",
    "        return com(nums, k)   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        _list = list(range(1,n+1))\n",
    "        return self.dfs(_list, k)\n",
    "        \n",
    "    def dfs(self, _list, k):\n",
    "        _len = len(_list)\n",
    "        \n",
    "        if k == 1:\n",
    "            return [[ele] for ele in _list]\n",
    "\n",
    "        if _len == k:\n",
    "            return [_list]\n",
    "        \n",
    "        result = []\n",
    "\n",
    "        for i, ele in enumerate(_list):\n",
    "            if i == _len - k:\n",
    "                res = [_list[i:]]\n",
    "            else:\n",
    "                res = self.dfs(_list[i + 1:], k - 1)\n",
    "                res = [[ele] + _res for _res in res]\n",
    "            result += res\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        _list = list(range(1,n+1))\n",
    "        return self.dfs(_list, k)\n",
    "        \n",
    "    def dfs(self, _list, k):\n",
    "        _len = len(_list)\n",
    "        \n",
    "        if k == 1:\n",
    "            return [[ele] for ele in _list]\n",
    "\n",
    "        if _len == k:\n",
    "            return [_list]\n",
    "        \n",
    "        result = []\n",
    "\n",
    "        for i, ele in enumerate(_list):\n",
    "            if i == _len - k:\n",
    "                res = [_list[i:]]\n",
    "            else:\n",
    "                res = self.dfs(_list[i + 1:], k - 1)\n",
    "                res = [[ele] + _res for _res in res]\n",
    "            result += res\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        combine = []\n",
    "        def dfs(n, k, pos):\n",
    "            if k==0:\n",
    "                res.append(combine[:])\n",
    "                return\n",
    "            if n-pos+1==k:\n",
    "                res.append(combine[:])\n",
    "                for i in range(pos, n+1):\n",
    "                    res[-1].append(i)\n",
    "                return\n",
    "\n",
    "            dfs(n, k, pos+1)\n",
    "            # for i in range(k):\n",
    "            #     combine.pop()\n",
    "            combine.append(pos)\n",
    "            dfs(n, k-1, pos+1)\n",
    "            combine.pop()\n",
    "        dfs(n, k, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if n < k:\n",
    "            return []\n",
    "        if k == 0 or n == 0:\n",
    "            return [[]]\n",
    "        return [*map(lambda l: [*l, n], self.combine(n - 1, k - 1)), *self.combine(n - 1, k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def updateans(path,curnumber):\n",
    "            nonlocal ans\n",
    "            if k-len(path) == n-curnumber+1:\n",
    "                np = path.copy()\n",
    "                for i in range(curnumber,n+1):\n",
    "                    np.append(i)\n",
    "                ans.append(np)\n",
    "                return \n",
    "            if len(path) == k:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            if curnumber>n:\n",
    "                return \n",
    "            updateans(path,curnumber+1)\n",
    "            np = path.copy()\n",
    "            np.append(curnumber)\n",
    "            updateans(np,curnumber+1)\n",
    "\n",
    "        updateans([],1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        # 简单递归\n",
    "        if k == 1:\n",
    "            return [[x] for x in range(1, n+1)]\n",
    "        res = []\n",
    "        for i in range(n, k-1, -1):\n",
    "            res = res + [x + [i] for x in self.combine(i-1, k-1)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        \n",
    "        def choose(next,rest):\n",
    "            if next>n:\n",
    "                return []\n",
    "            if rest==1:\n",
    "                return [[next]] + choose(next+1,rest)\n",
    "            \n",
    "            return [[next,*i] for i in choose(next+1,rest-1)] + choose(next+1,rest)\n",
    "        \n",
    "        return choose(1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def backtracking(n, k, ans):\n",
    "            if k == 0:\n",
    "                result.append(ans)\n",
    "            \n",
    "            for i in range(1, n+1):\n",
    "                # if i in ans:\n",
    "                #     continue\n",
    "                if len(ans) > 0 and i <= ans[-1]:\n",
    "                    continue\n",
    "                ans.append(i)\n",
    "                backtracking(n, k - 1, ans[:])\n",
    "                ans.pop()\n",
    "\n",
    "        \n",
    "        ans = []\n",
    "        result = []\n",
    "        backtracking(n, k, ans[:])\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if n == k:\n",
    "            return [list(range(1,n+1))]\n",
    "        if k == 1:\n",
    "            return [[i] for i in range(1,n+1)]\n",
    "        else:\n",
    "            wz_n = self.combine(n-1,k-1)\n",
    "            wo_n = self.combine(n-1,k)\n",
    "            return wo_n + [item+[n] for item in wz_n]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k == 0:\n",
    "            return [[]]\n",
    "        else:\n",
    "            res = []\n",
    "            for i in range(k, n+1):\n",
    "                combination = self.combine(i-1, k-1) \n",
    "                for c in combination:\n",
    "                    res.append(c+[i])\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        def dfs(start, k):\n",
    "            if k == 1:\n",
    "                #print([[i] for i in range(start, n - k + 2)])\n",
    "                return [[i] for i in range(start, n - k + 2)]\n",
    "            \n",
    "            ans = []\n",
    "            for i in range(start, n - k + 2): \n",
    "                nexs = dfs(i + 1, k - 1)\n",
    "                for nex in nexs:\n",
    "                    res = [i]\n",
    "                    res.extend(nex)\n",
    "                    ans.append(res)\n",
    "            \n",
    "            return ans\n",
    "\n",
    "\n",
    "        if n == 0:\n",
    "            return []\n",
    "\n",
    "        #res = []\n",
    "        \n",
    "        return dfs(1, k)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = set()\n",
    "        def func(i, kk, path):\n",
    "            if not kk:\n",
    "                res.add(tuple(path))\n",
    "                return\n",
    "            if n-i+1 < kk:\n",
    "                return\n",
    "            func(i+1, kk, path)\n",
    "            func(i+1, kk-1, path+[i])\n",
    "        func(1, k, [])\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        if k == 1:\n",
    "            return [[i] for i in range(1, n + 1)]\n",
    "\n",
    "        def gen(arr, number):\n",
    "            if number == 1:\n",
    "                return arr\n",
    "            elif number == 0:\n",
    "                return []\n",
    "            \n",
    "            result = []\n",
    "            for index, value in enumerate(arr):\n",
    "                remain_arr = arr[index + 1:]\n",
    "                tmp_result = gen(remain_arr, number - 1)\n",
    "                for item in tmp_result:\n",
    "                    if isinstance(item, list):\n",
    "                        result.append([value, *item])\n",
    "                    else:\n",
    "                        result.append([value, item])\n",
    "            return result\n",
    "        \n",
    "        return gen([i for i in range(1, n + 1)], k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        result=[[x+1] for x in range(n)]\n",
    "        for i in range(2,k+1):\n",
    "            last_result=result\n",
    "            result=[]\n",
    "            for item in last_result:\n",
    "                _max=item[-1]\n",
    "                if _max+k-i+1>n:\n",
    "                    continue\n",
    "                for j in range(_max+1,n+1):\n",
    "                    result.append(item+[j])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        que = deque()\n",
    "        for i in range(1, n+1):\n",
    "            que.append([i])\n",
    "        ret = []\n",
    "        while que:\n",
    "            tmp = que.popleft()\n",
    "            if len(tmp) == k:\n",
    "                ret.append(tmp)\n",
    "            else:\n",
    "                for i in range(tmp[-1]+1, n+1):\n",
    "                    tmp_copy = tmp + [i]\n",
    "                    que.append(tmp_copy)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans = self.reru(n,k)\n",
    "        return ans\n",
    "\n",
    "    def reru(self,n,k):\n",
    "        ans = []\n",
    "        if n<=0 or k<=0:\n",
    "            return False\n",
    "        if n == k:\n",
    "            t = list(range(1,n+1))\n",
    "            ans.append(t)\n",
    "        elif n>k:\n",
    "            r1 = self.reru(n-1,k-1)\n",
    "            r2 = self.reru(n-1,k)\n",
    "            if r1:\n",
    "                for i in range(len(r1)):\n",
    "                    ans.append(r1[i]+[n])\n",
    "            if r2:\n",
    "                for i in range(len(r2)):\n",
    "                    ans.append(r2[i])\n",
    "                if k==1:\n",
    "                    ans.append([n])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = []\n",
    "        self.resp = []\n",
    "\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        digits = list(range(1, n + 1))\n",
    "        self.backtracking(digits, 0, k)\n",
    "        return self.resp\n",
    "\n",
    "    def backtracking(self, digits, index, k):\n",
    "        if len(self.result) == k:\n",
    "            self.resp.append(self.result)\n",
    "            return\n",
    "\n",
    "        digits = digits[index:]\n",
    "        for i in range(len(digits)):\n",
    "            self.result.append(digits[i])\n",
    "            self.backtracking(digits, i + 1, k)\n",
    "            self.result = self.result[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        \n",
    "\n",
    "        self.A = []\n",
    "        self.result = []\n",
    "        def dfs(idx):\n",
    "            if len(self.A)==k:\n",
    "                self.result.append(self.A)\n",
    "                return\n",
    "            for i in range(idx+1,n+1):\n",
    "                self.A.append(i)\n",
    "                dfs(i)\n",
    "                self.A = self.A[:-1]\n",
    "\n",
    "        dfs(0)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def backtrack(path):\n",
    "            if path == []:\n",
    "                leftRange = 1\n",
    "            else:\n",
    "                leftRange = int(path[-1])+1\n",
    "            for i in range(leftRange, n+1):\n",
    "                path.append(i)\n",
    "                if len(path) >= k:\n",
    "                    res.append(path)\n",
    "                else:\n",
    "                    path = backtrack(path)\n",
    "                path = path[:-1]\n",
    "            return path\n",
    "        \n",
    "        a = backtrack(path)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        result={x+1:[[x+1]] for x in range(n)}\n",
    "        print(result)\n",
    "        for i in range(2,k+1):\n",
    "            last_result=result\n",
    "            result={}\n",
    "            for j in range(n):\n",
    "                result[j+1]=[]\n",
    "            for _max,v in last_result.items():\n",
    "                if _max+k-i+1>n:\n",
    "                    continue\n",
    "                for item in v:\n",
    "                    for j in range(_max+1,n+1):\n",
    "                        result[j].append(item+[j])\n",
    "        r_list=[]\n",
    "        for v in result.values():\n",
    "            r_list+=v\n",
    "        return r_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans=deque([[]])\n",
    "        lef=deque([[i+1 for i in range(n)]])\n",
    "        while len(ans[0])!=k:\n",
    "            while len(lef[0])!=0:\n",
    "                # print(ans)\n",
    "                # print(lef)\n",
    "                tmp=[i for i in lef[0]]\n",
    "                ans.append(ans[0]+[tmp[0]])\n",
    "                tmp.pop(0)\n",
    "                lef[0].pop(0)\n",
    "                lef.append(tmp)\n",
    "            ans.popleft()\n",
    "            lef.popleft()\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ans=deque([[]])\n",
    "        lef=deque([[i+1 for i in range(n)]])\n",
    "        while len(ans[0])!=k:\n",
    "            while len(lef[0])!=0:\n",
    "                # print(ans)\n",
    "                # print(lef)\n",
    "                tmp=[i for i in lef[0]]\n",
    "                ans.append(ans[0]+[tmp[0]])\n",
    "                tmp.pop(0)\n",
    "                lef[0].pop(0)\n",
    "                lef.append(tmp)\n",
    "            ans.popleft()\n",
    "            lef.popleft()\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        for mask in range(1 << n):\n",
    "            tmp=[]\n",
    "            for i in range(n):\n",
    "                if mask.bit_count() == k and mask & (1 << i):\n",
    "                    tmp.append(i+1)\n",
    "            if tmp:res.append(tmp)      \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        ret=[]\n",
    "        for i in range(2**n):\n",
    "            if i.bit_count()==k:\n",
    "                temp=[]\n",
    "\n",
    "                for j in range(i.bit_length()):\n",
    "                    if  (i >> j) & 1:\n",
    "                        temp.append(j+1)\n",
    "\n",
    "                ret.append(temp)\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
